home *** CD-ROM | disk | FTP | other *** search
/ MacTech 1 to 12 / MacTech-vol-1-12.toast / Source / MacTech® Magazine / Volume 08 - 1992 / 08.07 Nov⁄Dec 92 / Programmers' Challenge / pegs.c < prev   
Encoding:
C/C++ Source or Header  |  1992-09-10  |  6.5 KB  |  185 lines  |  [TEXT/KAHL]
  1. /*    Solution to the    August 1992 MacTutor Programmers' Challenge
  2.  *
  3.  *  Submitted by Greg Landweber    on September 9,    1992
  4.  *
  5.  *    Address:    10 Wallingford Drive
  6.  *                Princeton, NJ  08540
  7.  *    Phone:        (609) 452-2655
  8.  *  E-mail:        landwebe@math.rutgers.edu (Peter Landweber's account)
  9.  */
  10.  
  11. #define    max    13    /* The number of holes in a row    or column.
  12.                  * NOTE: I assume that the holes start with 0
  13.                  * if the holes    start with 1, change max to 14.
  14.                  */
  15.  
  16. void BandedPegs    (numPegs, pegsPtr, numEdgePegsPtr, edgePegsPtr,    areaPtr)
  17. short   numPegs;
  18. Point    *pegsPtr;
  19. short    *numEdgePegsPtr;
  20. Point    *edgePegsPtr;
  21. Fixed    *areaPtr;
  22. {
  23.     short    xLeft[max],xRight[max];     /* leftmost and rightmost peg in each row       */
  24.     short    top,bottom;                 /* top    and bottom rows containing pegs              */
  25.     short    x,y;                     /* horizontal and vertical coords. of peg       */
  26.     short    area;                     /* used to compute twice the enclosed area       */
  27.     short    numLeft,numRight;         /* number of pegs on left and right side      */
  28.     Point    leftPegs[max],rightPegs[max]; /* array of pegs on left and right       */
  29.     short    index;                     /* general use    array index                       */
  30.     Point    *pegPtr1,*pegPtr2;         /* for    stepping through arrays of Points       */
  31.  
  32. /* Fill    xLeft[v] and xRight[v] with the    h-coords
  33.  * of the leftmost and rightmost pegs in row v.
  34.  * If there are    no pegs    in row v, then set
  35.  *    xLeft[v]  = max, and
  36.  *        xRight[v] = -1.
  37.  * Note    that any pegs inbetween    the leftmost and
  38.  * rightmost pegs in a row will    automatically be
  39.  * in the interior of the rubber band polygon.
  40.  * This    reduces    the maximum number of pegs to 26.
  41.  */
  42.  
  43.     for ( index = 0; index < max; index++ )    {
  44.         xLeft [index] =    max;
  45.         xRight[index] =    -1;
  46.     }
  47.  
  48.     pegPtr1    = pegsPtr;
  49.     for ( index = numPegs; index > 0; index-- ) {
  50.         y = pegPtr1->v;
  51.         x = pegPtr1->h;
  52.         if ( x < xLeft [y] )
  53.             xLeft [y] = x;
  54.         if ( x > xRight[y] )
  55.             xRight[y] = x;
  56.         pegPtr1++;
  57.     }
  58.  
  59. /* Find    the bottom (lowest v) and top (highest v) rows containing pegs.    */
  60.  
  61.     bottom = -1;
  62.     while (    xLeft [++bottom] == max    );
  63.  
  64.     top = max;
  65.     while (    xLeft [--top] == max );
  66.  
  67. /* Fill    leftPegs[] with    a list of all the pegs
  68.  * on the left side of the convex polygon from
  69.  * the top (hi v) to the bottom    (lo v),    and put
  70.  * the number of those pegs - 1    in numLeft.
  71.  */
  72.  
  73.     leftPegs[0].h =    xLeft[top];         /* leftPegs[0]    is the topmost (highest v)  */
  74.     leftPegs[0].v =    top;             /* point on the left side of the polygon.  */
  75.     numLeft    = 0;                     /* Index of the last peg in    leftPegs[].    */
  76.  
  77.     for (y = top - 1; y >= bottom; y--)    /* Add pegs from the top to the bottom. */
  78.         if ( (x    = xLeft[y]) != max ) {    /* Check if there is a peg in row y.       */
  79.             pegPtr1    = leftPegs;            /* Note    thatpegPtr2    is the current peg */
  80.             pegPtr2    = pegPtr1++;        /* in the list and pegPtr1 is the next. */
  81.             for ( index = 0; index < numLeft; index++ )
  82.  
  83.    /* Is the peg at {x,y} to the left of   */
  84.    /* the line from *pegPtr1 to    *pegPtr2?  */
  85.                 if ( ( (x       - pegPtr1->h) * (pegPtr2->v - pegPtr1->v)    ) <
  86.                      ( (pegPtr2->h - pegPtr1->h) * (y  - pegPtr1->v)    ) )
  87.                     numLeft    = index;
  88.    /* If so, all the pegs from pegPtr1 on  */
  89.    /* will be to the right of the line       */
  90.    /* from {x,y} to *pegPtr2, and so we       */
  91.    /* remove them from the left    peg list.  */
  92.                 else                    /* If not, we go on to the next peg.       */
  93.                     pegPtr2    = pegPtr1++;
  94.             numLeft++;                    /* Tack {x,y} onto the end of the list. */
  95.             pegPtr1->v = y;
  96.             pegPtr1->h = x;
  97.         }
  98.  
  99. /* Fill    rightPegs[] with a list    of all the pegs
  100.  * on the right    side of    the convex polygon from
  101.  * the top (hi v) to the bottom    (lo v),    and put
  102.  * the number of those pegs - 1    in numRight.
  103.  */
  104.  
  105.     rightPegs[0].h = xRight[top];     /* rightPegs[0] is the    topmost    (highest v) */
  106.     rightPegs[0].v = top;             /* point on the right side of the polygon. */
  107.     numRight = 0;                     /* Index of the last peg in    rightPegs[].   */
  108.  
  109.     for (y = top - 1; y >= bottom; y--)    /* Add pegs from the top to the bottom. */
  110.         if ( (x    = xRight[y]) !=    max ) {    /* Check if there is a peg in row y.       */
  111.             pegPtr1    = rightPegs;        /* Note    that pegPtr2is the current peg */
  112.             pegPtr2    = pegPtr1++;        /* in the list and pegPtr1 is the next. */
  113.             for ( index = 0; index < numRight; index++ )
  114.  
  115.    /* Is the peg at {x,y} to the right of  */
  116.    /* the line from *pegPtr1 to    *pegPtr2?  */
  117.                 if ( ( (x       - pegPtr1->h) * (pegPtr2->v - pegPtr1->v)    ) >
  118.                      ( (pegPtr2->h - pegPtr1->h) * (y  - pegPtr1->v)    ) )
  119.                     numRight = index;
  120.    /* If so, all the pegs from pegPtr1 on  */
  121.    /* will be to the left of the line       */
  122.    /* from {x,y} to *pegPtr2, and so we       */
  123.    /* remove them from the right peg list. */
  124.                 else                    /* If not, we go on to the next peg.       */
  125.                     pegPtr2    = pegPtr1++;
  126.             numRight++;                    /* Tack {x,y} onto the end of the list. */
  127.             pegPtr1->v = y;
  128.             pegPtr1->h = x;
  129.         }
  130.  
  131. /* Copy    the contents of    numLeft[] and numRight[] into edgePegsPtr. */
  132.  
  133.     pegPtr2    = edgePegsPtr;
  134.  
  135.     pegPtr1    = leftPegs + 1;
  136.     for ( index = numLeft -    1; index > 0; index-- )
  137.         *(pegPtr2++) = *(pegPtr1++);
  138.  
  139.                                     /* Do the pegs all lie on the same line?       */
  140.                                     /* If so, the left and right are the same.       */
  141.     if ( *(    (long *)leftPegs + 1 ) != *( (long *)rightPegs + 1 ) ) {
  142.         pegPtr1    = rightPegs + 1;
  143.         for ( index = numRight - 1; index > 0; index-- )
  144.             *(pegPtr2++) = *(pegPtr1++);
  145.     }
  146.  
  147. /* Put all the pegs in the top and bottom rows into edgePegsPtr. */
  148.  
  149.     pegPtr1    = pegsPtr;
  150.     for ( index = numPegs; index > 0; index-- ) {
  151.         if ( (pegPtr1->v == top) || (pegPtr1->v    == bottom) )
  152.             *(pegPtr2++) = *pegPtr1;
  153.         pegPtr1++;
  154.     }
  155.  
  156. /* Figure out how many pegs there are touching the edge    of the polygon.    */
  157.  
  158.     *numEdgePegsPtr    = pegPtr2 - edgePegsPtr;
  159.  
  160. /* Compute twice the area to the left of the right side    of the polygon.    */
  161.  
  162.     area = 0;            /* The area of a trapezoid with    height h and parallel   */
  163.                         /* sides of length a and b is h*(a+b)/2.  Here we have  */
  164.                         /*        h = pegPtr2->v - pegPtr1->v,                       */
  165.                         /*        a = pegPtr2->h,  and     b = pegPtr1->h    .           */
  166.  
  167.     pegPtr1    = rightPegs;            /* Loop    through    all of the line segments on       */
  168.     for ( index = numRight;    index >    0; index-- ) {
  169.         pegPtr2    = pegPtr1++;        /* the right side of the convex polygon.       */
  170.         area +=    (pegPtr2->v - pegPtr1->v) * (pegPtr2->h    + pegPtr1->h);
  171.     }
  172.  
  173. /* Subtract twice the area to the left of the left side    of the polygon.    */
  174.  
  175.     pegPtr1    = leftPegs;                /* Loop    through    all of the line segments on       */
  176.     for ( index = numLeft; index > 0; index-- ) {
  177.         pegPtr2    = pegPtr1++;        /* the left side of the    convex polygon.       */
  178.         area -=    (pegPtr2->v - pegPtr1->v) * (pegPtr2->h    + pegPtr1->h);
  179.     }
  180.  
  181. /* Finally, divide by two and convert the result to type Fixed.    */
  182.  
  183.     *areaPtr = FixRatio( area, 2 );
  184. }
  185.